Những bằng chứng khảo cổ cho thấy những dấu tích của con người ngay từ cuối Thời kỳ Băng hà. Tuy nhiên do khí hậu khắc nghiệt, Oklahoma không có dân cư sinh sống cho đến khi một nhóm người da đỏ đến định cư trong khoảng giữa năm 850 và 1450 sau công nguyên[8]. Năm 1541, nhà thám hiểm người Tây Ban Nha Francisco Vasquez de Coronado đã đi qua Oklahoma. Nhưng sau đó, vùng này lại thuộc về lãnh thổ Louisiana của Pháp trước khi bán lại cho Mỹ vào năm 1803.

Hàng ngàn người thổ dân da đỏ thuộc "Năm bộ lạc văn minh" (Five Civilized Tribes) ở các bang Mississippi, Florida, Alabama, Georgia và Tennessee đã bị chính phủ Mỹ buộc phải rời bỏ quê hương để đến định cư tại vùng đất cằn cỗi Oklahoma trong Cuộc hành trình Nước mắt ("Trail of Tears") trong thập niên 1830[9]. Nhiều người thổ dân da đỏ đã chết trong chuyến hành trình gian khổ và đầy bất công này. Sau khi đến Oklahoma, họ cùng với các dân tộc da đỏ bản địa Osage và Quapaw tạo nên một vùng đất chỉ dành riêng cho người da đỏ, được gọi là Vùng lãnh thổ Người da đỏ ("Indian Territory"). Vùng lãnh thổ này được chính phủ Mỹ hứa không xâm phạm. Đến năm 1890, đã có 30 bộ tộc da đỏ sinh sống tại đây.

Tuy nhiên sự mở rộng đất đai của người da trắng đã dẫn đến Đạo luật Dawes năm 1887 cho phép người da trắng được vào Oklahoma định cư. Một nửa lãnh thổ của Oklahoma được mở cửa cho những đoàn di dân mới đến hoặc được mua bởi công ty đường sắt. Những cuộc "land run" để người da trắng chạy đua vào chiếm đất được tổ chức, trong đó có cuộc chạy đua chiếm đất năm 1889. Trước giờ khai cuộc, một số người khôn ngoan hơn đã vượt giới tuyến vào cắm mốc trước tại những vùng đất nhiều lợi thế. Do đó, Oklahoma ngày nay có biệt hiệu là Bang Người đến sớm ("Sooner State")[10].

Tiếp theo, Đạo luật Curius đã bãi bỏ hoàn toàn quyền lợi pháp lý của người thổ dân da đỏ. Ngày 16 tháng 11 năm 1907, Oklahoma chính thức trở thành tiểu bang thứ 46 của Hoa Kỳ.

Những mỏ dầu đầu tiên với trữ lượng lớn đã nhanh chóng được khai thác tại Oklahoma, mang lại sự hưng thịnh cho nền kinh tế tiểu bang. Thành phố Tulsa trở thành "thủ đô dầu khí của thế giới"[11]. Năm 1927, một thương nhân ở Oklahoma là Cyrus Avery đã phát động việc xây dựng Quốc lộ 66, con đường giao thông huyền thoại xuyên nước Mỹ.

Mặc dù Luật Jim Crow và có sự hiện diện của tổ chức phân biệt chủng tộc Ku Klux Klan, thành phố Tulsa vẫn có một trong những cộng đồng người da đen thịnh vượng nhất nước Mỹ. Thế nhưng vào năm 1921, cuộc Bạo động Chủng tộc Tulsa bùng nổ khiến 300 người chết và gây thiệt hại 1,8 triệu USD. Đến cuối thập niên 1920, các hoạt động của tổ chức phản động 3K phần lớn đã bị hạn chế.

Thập niên 1930, trận Bão Bụi ("Dust Bowl") xảy ra. Suốt nhiều năm liền, trời không có một giọt mưa, thời tiết khô hạn và những trận bão bụi mịt mù đã tàn phá nền nông nghiệp của Oklahoma và một số tiểu bang khác như Kansas, Texas, New Mexico và đẩy hàng ngàn nông dân đến chỗ phá sản, phải tìm đường sang miền tây nước Mỹ lập nghiệp. Trong suốt 20 năm, dân số của Oklahoma sụt giảm liên tục. Cuối cùng thời kỳ đen tối này kết thúc vào thập niên 1950 khi những dự án xây đập nước được tiến hành. Vào thập niên 1960, Oklahoma có 200 hồ nước nhân tạo, nhiều nhất liên bang. Hàng ngàn hồ chứa nước được xây dựng đã giúp phục hồi nền nông nghiệp Oklahoma nói riêng và toàn bộ kinh tế Oklahoma nói chung.

Năm 1995, Oklahoma chứng kiến vụ khủng bố kinh hoàng nhất nước Mỹ trước ngày 11 tháng 9 năm 2001. Cao ốc Alfred P. Murrah tại thành phố Oklahoma bị hai tên khủng bố Timothy McVaigh và Terry Nichols đặt bom đánh sập, khiến 168 người chết, trong đó có 19 trẻ em. McVeigh sau đó đã bị xử tử hình còn Nichols thì nhận án tù chung thân không ân xá[12].